# -*- coding: utf-8 -*-

'''
MAIN.py
Created on Junho de 2013
@authors: 
    Ricardo Barros, ESTIG,  EI pós-laboral n.º 5137
    Sergio Santos, ESTIG,  EI pós-laboral n.º 5626
'''


from random import randint
from time import clock
import matplotlib.pyplot as plt
from tabulate import tabulate #https://pypi.python.org/pypi/tabulate
from math import log10
import sys

#modulos dos algoritmos de ordenação
from maxheapify import MaxHeap
from insertion import insertionSort
from merge import mergeSort
from quick import quickSort
from bubble import bubbleSort
from radix import radixSortNumbers
from bucket import bucketSort
from comb import combSort



def main():
    #número de testes a efetuar para cada "conjunto de dados" 
    nTestes = 25
    
    #array multidimensional com os conjuntos de dados a ordenar
    #com [1, 1000, 3000, 5000, 7000, 9000] quantidade de dados
    Z = [1] + range(500, 5500, 500)
    
    #obter um array multidimensional com os dados a ordenar
    D = aleatorio(Z)    #dados aleatórios
    #D = crescente(Z)   #dados por ordem crescente
    #D = decrescente(Z) #dados por ordem decrescente
    
    computeALL(D, nTestes)  #ordenar, utilizando todos os algoritmos
    #computeONE(D, nTestes) #ordenar, utilizando cada um dos algoritmos um-a-um

   

def computeONE(D, nTestes):
    '''
    Obter os dados para um algoritmo de ordenação para gerar gráfico e 
    ficheiro com os resultados.
    Args:   D: array multidimensional com os dados a ordenar.
            nTestes: número de vezes para ordenar cada conjunto de dados.
    '''
    #THeapSort = computeHeapSort(D, nTestes)
    #plotResultONE(THeapSort, title=u'HeapSort')

    #TInsertSort = computeInsertSort(D, nTestes)
    #plotResultONE(T=TInsertSort, title=u'InsertSort')

    #TMergeSort = computeMergeSort(D, nTestes)
    #plotResultONE(T=TMergeSort, title=u'MergeSort')

    #TQuickSort = computeQuickSort(D, nTestes)
    #plotResultONE(T=TQuickSort, title=u'QuickSort')

    #TBubbleSort = computeBubbleSort(D, nTestes)
    #plotResultONE(T=TBubbleSort, title=u'BubbleSort')

    #TRadixSort = computeRadixSort(D, nTestes)
    #plotResultONE(T=TRadixSort, title=u'RadixSort')

    #TBucketSort = computeBucketSort(D, nTestes)
    #plotResultONE(T=TBucketSort, title=u'BucketSort')

    TCombSort = computeCombSort(D, nTestes)
    plotResultONE(T=TCombSort, title=u'CombSort')

def computeALL(D, nTestes):
    '''
    Obter os dados de todos os algoritmos de ordenação para gerar gráfico e 
    ficheiro com os resultados.
    Args:   D: array multidimensional com os dados a ordenar.
            nTestes: número de vezes para ordenar cada conjunto de dados.
    '''
    
    THeapSort = computeHeapSort(D, nTestes)
    TInsertSort = computeInsertSort(D, nTestes)
    TMergeSort = computeMergeSort(D, nTestes)
    TQuickSort = computeQuickSort(D, nTestes)
    TBubbleSort = computeBubbleSort(D, nTestes)
    TRadixSort = computeRadixSort(D, nTestes)
    TBucketSort = computeBucketSort(D, nTestes)
    TCombSort = computeCombSort(D, nTestes)
    
    plotResultALL([[THeapSort, "HeapSort"],
                   [TInsertSort, "InsertSort"],
                   [TMergeSort, "MergeSort"],
                   [TQuickSort, "QuickSort"],
                   [TBubbleSort, "BubbleSort"],
                   [TRadixSort, "RadixSort"],
                   [TBucketSort, "BucketSort"],
                   [TCombSort, "CombSort"]])




def plotResultALL(DADOS):
    '''
    Cria o gráfico onde mostra com os tempos dobtidos com todos os algoritmos de
    ordenação e grava os resultados num ficheiro txt.
    Args:   DADOS: array multidimensional (array:dados, string:titulo algoritmo)
                   com os dados obtidos de todos os algoritmos de ordenação.
    '''
    
    Xa = [n for n, media, var, desvio in DADOS[0][0]]
    
    plt.grid(True)
    plt.ylabel(u'T(n) - Tempo execução médio em segundos')
    plt.xlabel(u'n - Número de elementos')
    plt.title(u"Comparação algoritmos ordenação")

    for D in DADOS:
        plt.plot(Xa, [media for n, media, var, desvio in D[0]], label=u''+D[1])
    
    plt.legend()
    plt.savefig("DADOS/ALL_dados.png")
    #plt.show()
    
    #Gravar dados obtidos p/ficheiro
    arquivo = open('DADOS/ALL_dados.txt', 'w')
    
    headers = ["N", "Media", "Variancia", "Desvio padrao"]
    for D in DADOS:
        arquivo.write("\n" + D[1] + ":\n")
        arquivo.write( tabulate( D[0], headers, tablefmt="orgtbl", floatfmt=".15f"))
        
    arquivo.close()
    



def plotResultONE(T, title):
    '''
    Cria o gráfico e grava os dados resultados experimentais, comparando-o com
    os resultados teóricos previstos.
    Args:   T: array com os dados experimentais de um algoritmo
            title: string com o nome do algoritmo em questão
    '''
    #X array número de dados
    X = [n for n, media, var, desvio in T]
    
    #Y array com a média obtida
    Y = [media for n, media, var, desvio in T]
    
    #Z array com o resultados teóricos previstos
    if title == 'HeapSort':
        ct = (X[len(X)-1]*log10(X[len(X)-1]))/Y[len(Y)-1]
        Z = [(n*log10(n))/ct for n, media, var, desvio in T]
    if title == 'InsertSort':
        ct = (X[len(X)-1]**2)/Y[len(Y)-1]
        Z = [n**2/ct for n, media, var, desvio in T]
    if title == 'MergeSort':
        ct = (X[len(X)-1]*log10(X[len(X)-1]))/Y[len(Y)-1]
        Z = [(n*log10(n))/ct for n, media, var, desvio in T]
    if title == 'QuickSort':
        ct = (X[len(X)-1]**2)/Y[len(Y)-1]
        Z = [n**2/ct for n, media, var, desvio in T]
    if title == 'BubbleSort':
        ct = (X[len(X)-1]**2)/Y[len(Y)-1]
        Z = [n**2/ct for n, media, var, desvio in T]
    if title == 'RadixSort':
        ct = (T.__len__() * X[len(X)-1])/Y[len(Y)-1]
        Z = [ (T.__len__() * n)/ct for n, media, var, desvio in T]
    if title == 'BucketSort':
        ct = (X[len(X)-1])/Y[len(Y)-1]
        Z = [n/ct for n, media, var, desvio in T]
    if title == 'CombSort':
        ct = (X[len(X)-1]**2)/Y[len(Y)-1]
        Z = [(n**2)/ct for n, media, var, desvio in T]
    
    #Gravar os resultados para um ficheiro txt
    arquivo = open("DADOS/" + title + '_dados.txt', 'w')
    arquivo.write(title + "\n\n")
    headers = ["N", "Media", "Variancia", "Desvio padrao"]
    arquivo.write( tabulate(T, headers, tablefmt="orgtbl", floatfmt=".15f"))
    arquivo.close()

    #criar o gráfico
    plt.grid(True)
    plt.ylabel(u'T(n) - Tempo execução médio em segundos')
    plt.xlabel(u'n - Número de elementos')
    plt.title(title)
    plt.plot(X,Y,'-rs', label=u"resultado experimental")
    plt.plot(X,Z,'-*', label=u"resultado teorico")
    plt.legend()
    plt.savefig("DADOS/" + title + ".png")
    #plt.show()

def computeHeapSort(D, nTestes):
    '''
    Executa e obtém tempos de execução do algoritmo HeapSort
    Args:   D: array multidimensional com os dados a ordenar
    Return: T: array multidimensional tempos de execução obtidos
    '''
    T = []
    for n in range (len(D)):
        tempos = []
        print n
        for k in range(nTestes):
            mh = MaxHeap(D[n])
            t1 = clock()
            mh.heapsort()
            t2 = clock()
            tempos.append(t2-t1)
        tmp = calcularEstatistica(tempos)
        T.append((len(D[n]), tmp[0], tmp[1], tmp[2]))
    return T

def computeInsertSort(D, nTestes):
    '''
    Executa e obtém tempos de execução do algoritmo InsertSort
    Args: D: array multidimensional com os dados a ordenar
    Return: T: array multidimensional tempos de execução obtidos
    '''
    T = []
    for n in range (len(D)):
        tempos = []
        for k in range(nTestes):
            t1 = clock()
            insertionSort(D[n])
            t2 = clock()
            tempos.append(t2-t1)
        tmp = calcularEstatistica(tempos)
        T.append((len(D[n]), tmp[0], tmp[1], tmp[2]))
    return T

def computeBubbleSort(D, nTestes):
    '''
    Executa e obtém tempos de execução do algoritmo Bubble
    Args:   D: array multidimensional com os dados a ordenar
    Return: T: array multidimensional tempos de execução obtidos
    '''
    T = []
    for n in range (len(D)):
        print n, "/", len(D)
        tempos = []
        for k in range(nTestes):
            t1 = clock()
            bubbleSort(D[n])
            t2 = clock()
            tempos.append(t2-t1)
        tmp = calcularEstatistica(tempos)
        T.append((len(D[n]), tmp[0], tmp[1], tmp[2]))
    return T

def computeQuickSort(D, nTestes):
    '''
    Executa e obtém tempos de execução do algoritmo QuickSort
    Args:   D: array multidimensional com os dados a ordenar
    Return: T: array multidimensional tempos de execução obtidos
    '''
    T = []
    for n in range (len(D)):
        tempos = []
        print n
        for k in range(nTestes):
            t1 = clock()
            #p: posição inicial
            #r: posição final
            quickSort(D[n], p=0, r=(len(D[n])-1))
            t2 = clock()
            tempos.append(t2-t1)
        tmp = calcularEstatistica(tempos)
        T.append((len(D[n]), tmp[0], tmp[1], tmp[2]))
    return T

def computeMergeSort(D, nTestes):
    '''
    Executa e obtém tempos de execução do algoritmo MergeSort
    Args:   D: array multidimensional com os dados a ordenar
    Return: T: array multidimensional tempos de execução obtidos
    '''
    T = []
    for n in range (len(D)):
        tempos = []
        for k in range(nTestes):
            t1 = clock()
            #p: posição inicial
            #r: posição final
            mergeSort(D[n], p=0, r=len(D[n])-1)
            t2 = clock()
            tempos.append(t2-t1)
        tmp = calcularEstatistica(tempos)
        T.append((len(D[n]), tmp[0], tmp[1], tmp[2]))
    return T

def computeRadixSort(D, nTestes):
    '''
    Executa e obtém tempos de execução do algoritmo RadixSort
    Args:   D: array multidimensional com os dados a ordenar
    Return: T: array multidimensional tempos de execução obtidos
    '''
    T = []
    for n in range (len(D)):
        #print n, "/", len(D)
        tempos = []
        for u in range(nTestes):
            t1 = clock()
            radixSortNumbers(D[n])
            t2 = clock()
            tempos.append(t2-t1)
        tmp = calcularEstatistica(tempos)
        T.append((len(D[n]), tmp[0], tmp[1], tmp[2]))
    return T
    
def computeBucketSort(D, nTestes):
    '''
    Executa e obtém tempos de execução do algoritmo RadixSort
    Args:   D: array multidimensional com os dados a ordenar
    Return: T: array multidimensional tempos de execução obtidos
    '''
    T = []
    for n in range (len(D)):
        print n, "/", len(D)
        tempos = []
        for k in range(nTestes):
            t1 = clock()
            bucketSort(D[n])
            t2 = clock()
            tempos.append(t2-t1)
        tmp = calcularEstatistica(tempos)
        T.append((len(D[n]), tmp[0], tmp[1], tmp[2]))
    return T
    
def computeCombSort(D, nTestes):
    '''
    Executa e obtém tempos de execução do algoritmo CombSort
    Args:   D: array multidimensional com os dados a ordenar
    Return: T: array multidimensional tempos de execução obtidos
    '''
    T = []
    for n in range (len(D)):
        print n, "/", len(D)
        tempos = []
        for k in range(nTestes):
            t1 = clock()
            combSort(D[n])
            t2 = clock()
            tempos.append(t2-t1)
        tmp = calcularEstatistica(tempos)
        T.append((len(D[n]), tmp[0], tmp[1], tmp[2]))
    return T

def calcularEstatistica(tempos):
    media = reduce(lambda x, y: x + y, tempos) / len(tempos)
    var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos) 
    desvio = var**(1/2.0)  #calculo desvio padrão elevando pelo inverso.!
    return [media, var, desvio]
    
def aleatorio(Z):
    '''
    Cria um array multidimensional aleatório
    Args: Z: array que contém as dimensões para cada sub-array a gerar 
    Returns: T: o array multidimensional gerado
    '''
    count = 0
    T = len(Z)*[0]
    for n in Z:
        T[count] = [randint(0, n) for m in range (0, n)] #random.randint
        count = count + 1
    return T

def crescente(Z):
    '''
    Cria um array multidimencional ordenado por ordem crescente
    Args: Z: array que contém as dimensões para cada sub-array a gerar 
    Returns: T: o array multidimensional gerado
    '''
    count = 0
    T = len(Z)*[0]
    for n in Z:
        T[count] = range(1, n, 1)
        count = count + 1
    return T

def decrescente(Z):
    '''
    Cria um array multidimencional ordenado por ordem decrescente
    Args: Z: array que contém as dimensões para cada sub-array a gerar 
    Returns: T: o array multidimensional gerado
    '''
    count = 0
    T = len(Z)*[0]
    for n in Z:
        T[count] = range(1, n, -1)
        count = count + 1
    return T
    

if __name__ == '__main__':
    main()